# !/usr/bin/python
# -*- coding: utf-8 -*-
'''
@File    :   11_insertsort.py
@Time    :   2021/04/01 19:20:31
@Author  :   Qingxiang Zhang
@Version :   1.0
@Contact :   344285081@qq.com
@Desc    :   插入排序算法
@Software:    Vscode
'''
'''
插入算法，比较交换
最优时间复杂度：O（n）
最坏时间复杂度：O(n^2)
稳定性： 稳定的
'''
def insert_sort(aList):
    n = len(aList)    
    for j in range(1,n):    
        i = j  
        while i>0:  # 可以写成 for(j,0,-1)步长是负一
            if aList[i] < aList[i-1]:
                aList[i-1],aList[i] = aList[i],aList[i-1]
                i -= 1
            else:
                break
    return aList

if __name__=="__main__":
    aList = [3,5,6,8,4,1,3]
    print(insert_sort(aList))